import java.util.PriorityQueue;
import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 38917
 * Date: 2025/6/9
 * Time: 18:13
 */

public class Solution {
//    public int findKthLargest(int[] nums, int k) {
//        if (nums == null || nums.length < k) {
//            return -1;
//        }
//        //创建大根堆
//        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
//        for (int num : nums) {
//            queue.offer(num);
//        }
//        for (int i = 0; i < k - 1; i++) {
//            queue.poll();
//        }
//        return queue.peek();
//    }
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        int ret = solution.findKthLargest(new int[]{1,2,3,4,5,6,7}, 1);
//        System.out.println(ret);
//    }
    public int findKthLargest(int[] nums, int k) {
        return quickSort(nums,0,nums.length - 1,k);
    }
    private int quickSort(int[] nums, int low, int high, int k) {
        int key = nums[new Random().nextInt(high - low + 1) + low],left = low - 1,right = high + 1,index = low;
        while (index < right) {
            if (nums[index] < key) {
                swap(nums,++left,index++);
            }else if (nums[index] == key) {
                index++;
            }else {
                swap(nums,--right,index);
            }
        }
        int b = right - left - 1,c = high - right + 1;
        if (c >= k) {
            return quickSort(nums,right,high,k);
        } else if (b + c >= k) {
            return key;
        } else {
            return quickSort(nums,low,left,k - b - c);
        }
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int kthLargest = solution.findKthLargest(new int[]{7,3,2,5,6,4,1}, 2);
        System.out.println(kthLargest);
    }
}